package me.zhulu.amazonTest;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * User: herosea
 * Date: 14-4-23
 * Time: 下午8:44
 * To change this template use File | Settings | File Templates.
 */
public class Add {

    private static class Node {
        String value;
        Node next;

        Node(String value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        Node first = new Node("A", null);
        first = new Node("2", first);
        print(first);

        Node second = new Node("1", null);
        second = new Node("F", second);
        second = new Node("F", second);
        print(second);

        Node result = addHex(first, second);
        print(result);

        System.out.println();

        first = new Node("8", first);
        first = new Node("A", first);
        print(first);
        print(second);
        Node result2 = addHex(first, second);
        print(result2);
    }

    private static void print(Node node) {
        while(node != null) {
            System.out.print(node.value);
            node = node.next;
        }
        System.out.println();
    }

    public static Node addHex(Node first, Node second) {
        List<Integer> firstI = parse(first);
        List<Integer> secondI = parse(second);
        List<Integer> resultI = add(firstI, secondI);
        Node result = parse(resultI);
        return result;
    }

    private static Node parse(List<Integer> list) {
        Node first = null;
        for(int i = 0; i < list.size(); i++) {
            String value = Integer.toHexString(list.get(i));
            first = new Node(value, first);
        }
        return first;
    }

    private static List<Integer> parse(Node hexList) {
        Node current = hexList;
        List<Integer> result = new ArrayList();
        while(current != null) {
            result.add(Integer.valueOf(current.value, 16));
            current = current.next;
        }

        Collections.reverse(result);
        return result;
    }

    public static List<Integer> add(List<Integer> first, List<Integer> second) {
        int firstSize = first.size();
        int secondSize = second.size();
        int minSize = Math.min(firstSize, secondSize);
        int size = Math.max(firstSize, secondSize);

        List<Integer> fillList = null;
        if(firstSize > secondSize) {
            fillList = second;
        } else if (firstSize < secondSize) {
            fillList = first;
        }
        if (fillList != null) {
            for(int i = minSize; i < size; i++) {
                fillList.add(0);
            }
        }

        List<Integer> result = new ArrayList<Integer>();
        int lastValue = 0;
        for(int i = 0; i < size; i++) {
            int value = first.get(i) + second.get(i) + lastValue;
            if(value >= 16) {
                value = value - 16;
                lastValue = 1;
            } else {
                lastValue = 0;
            }
            result.add(value);
        }
        if(lastValue == 1){
            result.add(1);
        }
        return result;
    }
}
